﻿#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <numeric>


using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	
};

class Solution {
public:
	/*unordered_set<string> set;
	int max = 0;
	void dfs(string s, int index) {
		string tmp;
		for (int i = index; i < s.size(); i++) {
			tmp += s[i];
			if (set.find(tmp) == set.end()) {
				set.emplace(tmp);
				dfs(s, i + 1);
				set.erase(tmp);
			}
		}
		if (set.find(tmp) != set.end())
			return;
		max = max > set.size() ? max : set.size();
	}

	int maxUniqueSplit(string s) {
		dfs(s, 0);
		return max;
	}*/
	typedef long long ll;
	int maxProductPath(vector<vector<int>>& grid) {
		vector<vector<ll>> dp[2];
		dp[0].assign(grid.size(), vector<ll>(grid[0].size(), -1));
		dp[1].assign(grid.size(), vector<ll>(grid[0].size(), 1));
		ll tmp = 1;
		bool haszero = false;
		int row = grid.size();
		int col = grid[0].size();
		for (int i = 0; i < grid.size(); i++) {
			tmp *= (ll)grid[i][0];
			if (grid[i][0] == 0)
				haszero = true;
			if (tmp >= 0)
				dp[0][i][0] = tmp;
			else
				dp[1][i][0] = tmp;
		}
		tmp = 1;
		for (int i = 0; i < grid[0].size(); i++) {
			tmp *= (ll)grid[0][i];
			if (grid[0][i] == 0)
				haszero = true;
			if (tmp >= 0)
				dp[0][0][i] = tmp;
			else
				dp[1][0][i] = tmp;
		}

		for (int i = 1; i < grid.size(); i++) {
			for (int j = 1; j < grid[0].size(); j++) {
				if (grid[i][j] == 0) {
					dp[0][i][j] = 0;
					dp[1][i][j] = 0;
					haszero = true;
				}
				else if (grid[i][j] > 0) {
					ll t1 = dp[0][i - 1][j];
					ll t2 = dp[0][i][j - 1];
					dp[0][i][j] = t1 > t2 ? t1 : t2;
					dp[0][i][j] *= grid[i][j];
					ll t3 = dp[1][i - 1][j];
					ll t4 = dp[1][i][j - 1];
					dp[1][i][j] = t3 < t4 ? t3 : t4;
					dp[1][i][j] *= grid[i][j];
				}
				else {
					ll t1 = dp[0][i - 1][j];
					ll t2 = dp[0][i][j - 1];
					dp[1][i][j] = t1 > t2 ? t1 : t2;
					dp[1][i][j] *= grid[i][j];
					ll t3 = dp[1][i - 1][j];
					ll t4 = dp[1][i][j - 1];
					dp[0][i][j] = t3 < t4 ? t3 : t4;
					dp[0][i][j] *= grid[i][j];
				}
			}
		}
		if(haszero)
			return dp[0][row - 1][col - 1] >= 0 ? dp[0][row - 1][col - 1] % 1000000007 : 0;
		else
			return dp[0][row - 1][col - 1] >= 0 ? dp[0][row - 1][col - 1] % 1000000007 : -1;
	}
};


int main()
{
	Solution sol;
	vector<vector<int>> test = { {1, 4, 4, 0},{-2, 0, 0, 1},{1, -1, 1, 1} };
	vector<vector<int>> test2 = { {1, 3},{0, -4} };
	
	vector<int> t = { 1,2,3 };
	sol.maxProductPath(test2);
	cout <<endl;
}
